


#ifndef _HEAP__H_
#define _HEAP__H_


#include "stl_list.h"


/// <summary>
/// 单向循环链表结构体。只记录尾节点，使用尾节点可以方便尾部插入数据，
/// 尾节点的下一个节点是头节点。
/// 如果是按序插入，就是从小往大排列，头节点是最小的节点。
/// </summary>
typedef struct  ___heap__
{
	Datapointer* data_buffer;   //数据数组缓存，为了方便下标计算，索引从1开始。
	// 堆的根节点是1，下标k的节点左子树是2k，右子树是2k+1. (2k+1 <= count)的情况。

	int Capacity;     //队列容量。实际容量是Capacity-1
	int count;        //当前节点数量。因为索引从1开始，因此最后一个节点是data_buffer[count],count<Capacity;
	bool is_MaxHeap;  //是否大根堆。

	/// 比较函数（key1,key2）: key1 > key2返回1，key1 < key2返回-1,key1 = key2返回0.
	int (*match)(Datapointer key1, Datapointer key2);
}Heap;



/// <summary>
/// 分配堆的内存
/// </summary>
/// <param name="heap">堆</param>
/// <param name="capacity">堆的数组容量,实际容量是capacity-1</param>
/// <param name="is_MaxHeap">是否大根堆</param>
/// <param name="c">比较函数(key1,key2):key1大于key2返回1,key1小于key2返回-1,key1等于key2返回0</param>
void Heap_allocate(Heap* heap, int capacity, bool is_MaxHeap, int (*c)(Datapointer, Datapointer));

/// <summary>
/// 释放堆的内存。
/// </summary>
/// <param name="heap"></param>
void Heap_deallocate(Heap* heap);


/// <summary>
/// 将链表的元素Datapointer构建成堆。
/// </summary>
/// <param name="heap">堆</param>
/// <param name="list">链表</param>
void Heap_build_with_list(Heap* heap, List* list);

/// <summary>
/// 将数组的元素构建成堆。
/// </summary>
/// <param name="heap">堆</param>
/// <param name="dat">数据数组</param>
/// <param name="dat_len">数组长度</param>
void Heap_build_with_array(Heap* heap, Datapointer* dat, int dat_len);

/// <summary>
/// 堆排序，堆排序后，现有的堆会倒转，原来的大根堆会变成小根堆，小根堆变成大根堆。
/// 时间复杂度：O(n*Log(n))
/// 如果原来是大根堆，排序后是从小到大，大根堆变成小根堆。
/// 如果原来是小根堆，排序后是从大到小，小根堆变成大根堆。
/// </summary>
/// <param name="heap"></param>
void Heap_sort(Heap* heap);

/// <summary>
/// 往堆中推入一个元素，时间复杂度：Log(n)
/// </summary>
/// <param name="heap">堆</param>
/// <param name="datap">数据指针</param>
/// <returns>true: 成功插入；false：插入失败，堆已满</returns>
bool Heap_push(Heap* heap, Datapointer datap);

/// <summary>
/// 弹出堆顶元素，时间复杂度：Log(n)
/// </summary>
/// <param name="heap"></param>
/// <returns>堆顶元素。NULL：弹出失败，堆已空</returns>
Datapointer Heap_pop(Heap* heap);







void test_heap(void);


#endif

//

